class TrieNode {
    constructor() {
        this.children = new Array(26).fill(null);
        this.word = null;
    }
}

function buildTrie(words) {
    const root = new TrieNode();
    for (const s of words) {
        let curr = root;
        for (const c of s) {
            const index = c.charCodeAt(0) - 'a'.charCodeAt(0);
            if (curr.children[index] === null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
        curr.word = s;
    }
    return root;
}

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(board, words) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    const rows = board.length, cols = board[0].length
    const visited = new Array(rows).fill(0).map(() => new Array(cols).fill(false))
    const res = []

    const inArea = (row, col) => {
        return row >= 0 && row < rows && col >= 0 && col < cols;
    }

    const dfs = (row, col, node) => {
        const c = board[row][col];
        const index = c.charCodeAt(0) - 'a'.charCodeAt(0);
        if (node.children[index] == null) return

        node = node.children[index]
        if (node.word != null) {
            res.push(node.word)
            node.word = null
        }

        visited[row][col] = true
        for (let dir of dirs) {
            const nextRow = row + dir[0]
            const nextCol = col + dir[1]
            if (inArea(nextRow, nextCol) && !visited[nextRow][nextCol]) {
                dfs(nextRow, nextCol, node)
            }
        }
        visited[row][col] = false
    }

    const root = buildTrie(words)
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            dfs(row, col, root)
        }
    }

    return res;
};